//
// Created by Administrator on 2024/6/7.
//
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#define MaxSize 50
using namespace std;
/**
 * m[i][j] = 0 --- i = j
 * m[i][j] = min( m[i][k] + m[k + 1][j] + q(i-1)*q(k)*q(j) )
 *  i <= k < j
 * @param p 
 * @param n 
 * @return 
 */

int Matrix_chain(int * p, int n){
    int m[MaxSize][MaxSize]; // 二维数组存储中间结果
    int s[MaxSize][MaxSize]; // 二维数组存储中间结果
    int q;
    
    // 初始化相同的代价为0
    for (int i = 1; i <= n; ++i) {
        m[i][i] = 0;
    }

    /**
     * 自上向下计算
     */
    for (int r = 2; r <= n; ++r) {
        for (int i = 1; i <= n - r + 1; ++i) { // 对角线都为0
            int j = i + r - 1; // 当 i = 1， j = 2， 此时是为第一个计算结果
            m[i][j] = INT_MAX;
            for (int k = i; k < j; ++k) {
//                q = min(q, m[i][k] + m[k + 1][j] + p[i-1] * p[k] * p[j]);
                q = m[i][k] + m[k + 1][j] + p[i-1] * p[k] * p[j];
                s[i][j] = i;
                if(q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }
    return m[1][n];
}

int main(){
    int d[] = {5, 10, 15, 10, 20, 10};
    int n = sizeof(d) / sizeof(d[0]);
    int minNum = Matrix_chain(d, n - 1);
//    cout<<minNum;
    printf("最小代价：%d\n", minNum);
    return 0;
}
